package oj.OR36;

import oj.ListNode;

/**
 * 链表的回文结构
 * 回文：上海自来水来自海上
 * 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
 * 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
 */
public class Solution {
    private int sizeOf(ListNode head){
        int count=0;
        for (ListNode cur=head; cur!=null ;cur=cur.next ) {
            count++;
        }
        return  count;
    }
    private ListNode middleNode(ListNode head){
        int size=sizeOf(head);
        for(int i=0;i<size/2;i++){
            head= head.next;
        }
        return head;
    }
    private ListNode reverse(ListNode head){
        ListNode fakeHead=new ListNode();
        fakeHead.next=head;
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode curLast=cur.next;
            cur.next=pre;
            pre=cur;
            cur=curLast;
        }
        return pre;
    }
    public boolean chkPalindrome(ListNode A) {
        // write code here
        ListNode B1=A;
        // 找到链表的中间结点
        ListNode midNode=middleNode(A);
        // 以中间结点为头结点进行逆置
        ListNode B2=reverse(midNode);
        // 全部相等：回文  true
        // 存在不相等：不是回文 false
        while(B1!=null&&B2!=null){
            if(B1.val!=B2.val){
                // 存在不相等
                return false;
            }
            B1=B1.next;
            B2=B2.next;
        }
        // 全部相等
        return true;
    }
}
